package class04

func preInToPos(pre, in []int) []int {
	N := len(pre)-1
	pos := make([]int, len(pre))
	preInToPosProcess(pre, 0, N, in, 0,N, pos, 0, N)
	return pos
}

func preInToPosProcess(
	pre []int, pl, pr int,
	in  []int, il, ir int,
	pos []int, al, ar int,
	){
	if pl > pr {
		return
	}
	if pl == pr {
		pos[al] = pre[pl]
		return
	}
	preNum := pre[0]
	// 该部分可优化为map
	mid := -1
	for i:=il ;i<=ir; i++ {
		if in[i] == preNum {
			mid = i
		}
	}
	pos[ar] = preNum
	leftLen := mid - il
	preInToPosProcess(pre, pl+1, pl+leftLen, in, il, mid-1, pos, al, al+leftLen-1)
	preInToPosProcess(pre, pl+leftLen+1, pr, in, mid+1, ir, pos, al+leftLen, ar-1)
}